Script:
Functional data structures
Headline
Functional data structures in Haskell
Description
Let's at the implementation of concrete data structures and abstract data types in functional style. Most importantly, those implementations do not perform mutations of existing data structures. Modifications on data are modeled by means of rebuilding an appropriately adjusted copy. (We will discuss that this is not necessarily inefficient, as one may think at first.) We demonstrate functonal data structures for stacks, binary search trees, and (skew) heaps. We also discuss the notion of abstract data types where one aims at hiding the concrete representation of a data structure with the intention to focus instead on the properties of the data types and also enabling switching implementations more easily thereby. We also cover the domain of unparsing or pretty printing (i.e., rendering structures as text) to discuss a more advanced example of an abstract data type and the closely related notion of combinator library.
Material
More focused on concrete data structures:
Concepts
- Concrete data type
- Functional data structure
- Stack
- Binary search tree
- Skew heap
- Abstract data type
- Reverse Polish notation as an illustrative application of Stack
- Functions as data as an advanced technique
- Combinator library as a functional programming form of abstract data type
- Unparsing or pretty printing as a domain benefitting from an ADT approach
- Amortized analysis
- Lazy evaluation
Technologies
- Technology:HughesPJ for pretty printing
Features
Contributions
Further reading
Ralf Lämmel
edited this article at
Fri, 08 May 2026 16:10:28 +0200
User contributions
User edits
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.